"""
【题目】
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:
	Given nums = [2, 7, 11, 15], target = 9,
	Because nums[0] + nums[1] = 2 + 7 = 9,
	return [0, 1].

【题目大意】
在数组中找到 2 个数之和等于给定值的两个数字，结果返回 2 个数字在数组中的下标。（假设只有两个数相加等于给定值，且一个数不能使用两次）

【解题思路】
这道题最优的做法时间复杂度是 O(n)。
顺序扫描数组，对每一个元素，在 map 中找能组合给定值的另一半数字，如果找到了，直接返回 2 个数字的下标即可。如果找不到，就把这个数字存入 map 中，等待扫到“另一半”数字的时候，再取出来返回结果。

【注意事项】
1、一个数不能用两次
2、数组可以出现相同的数字
"""

# coding=utf-8
import random


def two_sum(nums, target):
    for n in nums:
        # 记录当前值索引并从列表移出当前值（排除相同值的影响）
        index1 = nums.index(n)
        nums.remove(n)
        # 获取差值
        diff_num = target - n
        if diff_num in nums:
            index2 = nums.index(diff_num) + 1
            return [index1, index2]
        # 如果无匹配结果，则还原移出值
        nums.insert(index1, n)


ns = [random.randint(1, 10) for i in range(6)]
tg = 10
print("数组：%s" % ns)
print("和值：%s" % tg)
print("两数索引值：%s" % str(two_sum(ns, tg)))
